#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "../include/tree.h"
#include "../include/queue.h"

typedef struct node_s {
	int a;
	queue_t queue;	
	tree_t tree;
}node_t;

#define N 10

void printSons(tree_t * unit) {
	tree_t * p;
	node_t * pnode;
	int i = 0;
	while(1) {
		p = tree_get_son(unit, i);
		if (p == NULL) {
			break;	
		}
		pnode = entry(p, node_t, tree);
		i++;
		printf("%d ", pnode->a);
	} 	
}
void check_tree_is_empty() {
	tree_t head;	
	node_t node;
	

	init_head(tree_t, &head);	


	if( !tree_is_empty(&head) ){
		printf("wrong1:tree_is_emtpy\n");
		return ;
	} 	
	
        tree_add_son(&head, &(node.tree));
	
	if ( tree_is_empty(&head) ){
		printf("wrong2: tree_is_empty\n");
		return ;
	}
	tree_del_son(&head);
	
	if( !tree_is_empty(&head) ){
		printf("wrong3:tree_is_emtpy\n");
		return ;
	} 	

        tree_add_son(&head, &(node.tree));
	if ( tree_is_empty(&head) ){
		printf("wrong4: tree_is_empty\n");
		return ;
	}

	tree_del_son_all(&head);
	if( !tree_is_empty(&head) ){
		printf("wrong5:tree_is_emtpy\n");
		return ;
	} 	
	
	printf("right: tree_is_empty\n");
	
	
}
void check_tree_empty() {
	tree_t head;
	node_t node;
	
	init_head(tree_t, &head);
	
	head.first_son = &(node.tree);
	
	tree_empty(&head);
	if (! tree_is_empty(&head)) {
		printf("wrong1: tree_empty\n");
		return ;
	} 
	printf("right: tree_empty\n");
}

void check_tree_is_head() {
	tree_t head;
	node_t node;

	memset(&head, 0x00, sizeof(head));
	if (tree_is_head(&head)) {
		printf("wrong1: tree_is_head\n");
		return ;
	}
	init_head(tree_t, &head);	
	if (!tree_is_head(&head)) {
		printf("wrong2: tree_is_head\n"); 
		return ;
	}		
	printf("right: tree_is_head\n");
}

void check_tree_add_son() {
	tree_t head;
	int i = 0;
	node_t node[N];
	node_t * pnode;
	
	memset(&node, 0x00, sizeof(node));
	init_head(tree_t, &head);

	for (i = 0; i < N; ++i) {
		node[i].a = i;
	}
	tree_add_son(&head, &(node[0].tree));
	tree_add_son(&(node[0].tree), &(node[1].tree));
	tree_add_son(&(node[0].tree), &(node[2].tree));
	tree_add_son(&(node[1].tree), &(node[3].tree));
	tree_add_son(&(node[2].tree), &(node[7].tree));
	tree_add_son(&(node[2].tree), &(node[8].tree));
	tree_add_son(&(node[3].tree), &(node[4].tree));
	tree_add_son(&(node[3].tree), &(node[5].tree));
	tree_add_son(&(node[3].tree), &(node[6].tree));
	tree_add_son(&(node[8].tree), &(node[9].tree));

	pnode = entry(head.first_son, node_t, tree);
	if (pnode->a != 0) {
		printf("wrong1: tree_add_son\n");
		return ;
	}	
	pnode =entry(head.first_son->first_son, node_t, tree);
	if (pnode->a != 2) {
		printf("wrong2: tree_add_son\n");
		return ;
	}	
	pnode =entry(head.first_son->first_son->brother_right, node_t, tree);
	if (pnode->a != 1) {
		printf("wrong3: tree_add_son\n");
		return ;
	}	
	pnode =entry(head.first_son->first_son->brother_left, node_t, tree);
	if (pnode->a != 1) {
		printf("wrong4: tree_add_son\n");
		return ;
	}	
	pnode =entry(head.first_son->first_son->first_son, node_t, tree);
	if (pnode->a != 8) {
		printf("wrong5: tree_add_son\n");
		return ;
	}	
	pnode =entry(head.first_son->first_son->first_son->first_son, node_t, tree);
	if (pnode->a != 9) {
		printf("wrong6: tree_add_son\n");
		return ;
	}	
	pnode =entry(head.first_son->first_son->first_son->first_son->brother_right, node_t, tree);
	if (pnode->a != 9) {
		printf("wrong7: tree_add_son\n");
		return ;
	}	
	pnode =entry(head.first_son->first_son->first_son->first_son->brother_left, node_t, tree);
	if (pnode->a != 9) {
		printf("wrong8: tree_add_son\n");
		return ;
	}	
	pnode =entry(head.first_son->first_son->brother_right->first_son, node_t, tree);
	if (pnode->a != 3) {
		printf("wrong9: tree_add_son\n");
		return ;
	}	
	pnode =entry(head.first_son->first_son->brother_right->first_son->first_son, node_t, tree);
	if (pnode->a != 6) {
		printf("wrong10: tree_add_son\n");
		return ;
	}	
	pnode =entry(head.first_son->first_son->brother_right->first_son->first_son->brother_right, node_t, tree);
	if (pnode->a != 5) {
		printf("wrong11: tree_add_son\n");
		return ;
	}	
	pnode =entry(head.first_son->first_son->brother_right->first_son->first_son->brother_left, node_t, tree);
	if (pnode->a != 4) {
		printf("wrong12: tree_add_son\n");
		return ;
	}	
	pnode =entry(head.first_son->first_son->brother_right->first_son->first_son->brother_left->brother_left, node_t, tree);
	if (pnode->a != 5) {
		printf("wrong12: tree_add_son\n");
		return ;
	}	
	
	printf("right: tree_add_son\n");
	return;	
}

void printTree(tree_t * head) {

	queue_t qhead;
	tree_t * ptree;
	queue_t * pqueue;
	node_t * pnode, *p;
	int i = 0;

	init_head(queue_t, &qhead);

	pnode = entry(tree_get_root(head), node_t, tree);
	queue_push(&qhead, &(pnode->queue));
	
	while ((pqueue = queue_pop(&qhead)) != NULL) {
		pnode = entry(pqueue, node_t, queue);
		printf("%d ", pnode->a);					
		for (i = 0; (ptree = tree_get_son(&(pnode->tree), i)) != NULL; ++i) {
			p = entry(ptree, node_t, tree);
			queue_push(&qhead, &(p->queue));
		}		
	}
}
void check_tree_is_exist() {
	tree_t head;
        int i = 0;
        node_t node[N];
        node_t * pnode;

	memset(&node, 0x00, sizeof(node));
        init_head(tree_t, &head);

        for (i = 0; i < N; ++i) {
                node[i].a = i;
        }
	
	for (i = 0; i < N; ++i) {
		if (tree_is_exist(&head, &(node[i].tree))) {
			printf("wrong1: tree_is_exist\n");
		}
	}
        tree_add_son(&head, &(node[0].tree));
        tree_add_son(&(node[0].tree), &(node[1].tree));
        tree_add_son(&(node[0].tree), &(node[2].tree));
        tree_add_son(&(node[1].tree), &(node[3].tree));
        tree_add_son(&(node[2].tree), &(node[7].tree));
        tree_add_son(&(node[2].tree), &(node[8].tree));
        tree_add_son(&(node[3].tree), &(node[4].tree));
        tree_add_son(&(node[3].tree), &(node[5].tree));
        tree_add_son(&(node[3].tree), &(node[6].tree));
        tree_add_son(&(node[8].tree), &(node[9].tree));	
	for (i = 0; i < N; ++i) {
		if (!tree_is_exist(&head, &(node[i].tree))) {
			printf("wrong2: tree_is_exist\n");
		}
	}
	printf("right: tree_is_exist\n");
}

void check_tree_is_root() {
	tree_t head;
        int i = 0;
        node_t node[N];
        node_t * pnode;

        memset(&node, 0x00, sizeof(node));
        init_head(tree_t, &head);

        for (i = 0; i < N; ++i) {
                node[i].a = i;
        }

        for (i = 0; i < N; ++i) {
                if (tree_is_root(&(node[i].tree))) {
                        printf("wrong1: tree_is_root\n");
			return;
                }
        }
        tree_add_son(&head, &(node[0].tree));
        tree_add_son(&(node[0].tree), &(node[1].tree));
        tree_add_son(&(node[0].tree), &(node[2].tree));
        tree_add_son(&(node[1].tree), &(node[3].tree));
        tree_add_son(&(node[2].tree), &(node[7].tree));
        tree_add_son(&(node[2].tree), &(node[8].tree));
        tree_add_son(&(node[3].tree), &(node[4].tree));
        tree_add_son(&(node[3].tree), &(node[5].tree));
        tree_add_son(&(node[3].tree), &(node[6].tree));
        tree_add_son(&(node[8].tree), &(node[9].tree));
        for (i = 1; i < N; ++i) {
                if (tree_is_root(&(node[i].tree))) {
                        printf("wrong2: tree_is_root\n");
			return ;
                }
        }		
	if (!tree_is_root(&(node[0].tree))) {
		printf("wrong3: tree_is_root\n");
		return ;
	}
	printf("right: tree_is_root\n");
}

void check_tree_get_son() {
	tree_t head;
	tree_t * ptree;
        int i = 0;
        node_t node[N];
        node_t * pnode;

        memset(&node, 0x00, sizeof(node));
        init_head(tree_t, &head);

        for (i = 0; i < N; ++i) {
                node[i].a = i;
        }
        tree_add_son(&head, &(node[0].tree));
        tree_add_son(&(node[0].tree), &(node[1].tree));
        tree_add_son(&(node[0].tree), &(node[2].tree));
        tree_add_son(&(node[1].tree), &(node[3].tree));
        tree_add_son(&(node[2].tree), &(node[7].tree));
        tree_add_son(&(node[2].tree), &(node[8].tree));
        tree_add_son(&(node[3].tree), &(node[4].tree));
        tree_add_son(&(node[3].tree), &(node[5].tree));
        tree_add_son(&(node[3].tree), &(node[6].tree));
        tree_add_son(&(node[8].tree), &(node[9].tree));
	
	pnode = entry(tree_get_son(&(node[0].tree), 0), node_t, tree);
	if (pnode->a != 2) {
		printf("wrong1: tree_get_son\n");
		return;
	}
	pnode = entry(tree_get_son(&(node[0].tree), 1), node_t, tree);
	if (pnode->a != 1) {
		printf("wrong2: tree_get_son\n");
		return;
	}
	ptree = tree_get_son(&(node[0].tree), 2);
	if (ptree !=  NULL) {
		printf("wrong3: tree_get_son \n" );
		return;
	}
	printf("right: tree_get_son\n");
}


void check_tree_get_father(){
	tree_t head;
        tree_t * ptree;
        int i = 0;
        node_t node[N];
        node_t * pnode;

        memset(&node, 0x00, sizeof(node));
        init_head(tree_t, &head);

        for (i = 0; i < N; ++i) {
                node[i].a = i;
        }
        tree_add_son(&head, &(node[0].tree));
        tree_add_son(&(node[0].tree), &(node[1].tree));
        tree_add_son(&(node[0].tree), &(node[2].tree));
        tree_add_son(&(node[1].tree), &(node[3].tree));
        tree_add_son(&(node[2].tree), &(node[7].tree));
        tree_add_son(&(node[2].tree), &(node[8].tree));
        tree_add_son(&(node[3].tree), &(node[4].tree));
        tree_add_son(&(node[3].tree), &(node[5].tree));
        tree_add_son(&(node[3].tree), &(node[6].tree));
        tree_add_son(&(node[8].tree), &(node[9].tree)); 
	
	if (tree_get_father(&head) != &head) {
		printf("wrong1: tree_get_father\n");
		return ;
	}
	if (tree_get_father(&(node[0].tree)) != &head) {
		printf("wrong1: tree_get_father\n");
		return ;
	}
	if (tree_get_father(&(node[1].tree)) != &(node[0].tree)) {
		printf("wrong1: tree_get_father\n");
		return ;
	}
	if (tree_get_father(&(node[3].tree)) != &(node[1].tree)) {
		printf("wrong1: tree_get_father\n");
		return ;
	}
	if (tree_get_father(&(node[7].tree)) != &(node[2].tree)) {
		printf("wrong1: tree_get_father\n");
		return ;
	}
	if (tree_get_father(&(node[8].tree)) != &(node[2].tree)) {
		printf("wrong1: tree_get_father\n");
		return ;
	}
	if (tree_get_father(&(node[4].tree)) != &(node[3].tree)) {
		printf("wrong1: tree_get_father\n");
		return ;
	}
	if (tree_get_father(&(node[5].tree)) != &(node[3].tree)) {
		printf("wrong1: tree_get_father\n");
		return ;
	}
	if (tree_get_father(&(node[6].tree)) != &(node[3].tree)) {
		printf("wrong1: tree_get_father\n");
		return ;
	}
	if (tree_get_father(&(node[9].tree)) != &(node[8].tree)) {
		printf("wrong1: tree_get_father\n");
		return ;
	}
	printf("right: tree_get_father\n");
}

void check_tree_get_head() {
	tree_t head;
        tree_t * ptree;
        int i = 0;
        node_t node[N];
        node_t * pnode;

        memset(&node, 0x00, sizeof(node));
        init_head(tree_t, &head);

        for (i = 0; i < N; ++i) {
                node[i].a = i;
        }
        tree_add_son(&head, &(node[0].tree));
        tree_add_son(&(node[0].tree), &(node[1].tree));
        tree_add_son(&(node[0].tree), &(node[2].tree));
        tree_add_son(&(node[1].tree), &(node[3].tree));
        tree_add_son(&(node[2].tree), &(node[7].tree));
        tree_add_son(&(node[2].tree), &(node[8].tree));
        tree_add_son(&(node[3].tree), &(node[4].tree));
        tree_add_son(&(node[3].tree), &(node[5].tree));
        tree_add_son(&(node[3].tree), &(node[6].tree));
        tree_add_son(&(node[8].tree), &(node[9].tree));	
	
	for (i = 0; i < N; ++i) {
		if (tree_get_head(&(node[0].tree)) != &head) {
			printf("wrong1: tree_get_head\n");
		}
	}
	if (tree_get_head(&head) != &head) {
		printf("wrong2: tree_get_head\n");
	}
	printf("right: tree_get_head\n");
}

void check_tree_get_root() {
	tree_t head;
        tree_t * ptree;
        int i = 0;
        node_t node[N];
        node_t * pnode;

        memset(&node, 0x00, sizeof(node));
        init_head(tree_t, &head);

        for (i = 0; i < N; ++i) {
                node[i].a = i;
        }
	if (tree_get_root(&head) != NULL) {
		printf("wrong1: tree_get_root\n");
		return;
	}
        tree_add_son(&head, &(node[0].tree));
        tree_add_son(&(node[0].tree), &(node[1].tree));
        tree_add_son(&(node[0].tree), &(node[2].tree));
        tree_add_son(&(node[1].tree), &(node[3].tree));
        tree_add_son(&(node[2].tree), &(node[7].tree));
        tree_add_son(&(node[2].tree), &(node[8].tree));
        tree_add_son(&(node[3].tree), &(node[4].tree));
        tree_add_son(&(node[3].tree), &(node[5].tree));
        tree_add_son(&(node[3].tree), &(node[6].tree));
        tree_add_son(&(node[8].tree), &(node[9].tree));

        for (i = 0; i < N; ++i) {
                if (tree_get_root(&(node[0].tree)) != &(node[0].tree)) {
                        printf("wrong2: tree_get_root\n");
                }
        }
        if (tree_get_root(&head) != &(node[0].tree)) {
                printf("wrong2: tree_get_root\n");
        }
        printf("right: tree_get_root\n");	
}

void check_tree_del_son_all() {
	tree_t head;
        tree_t * ptree;
        int i = 0;
        node_t node[N];
        node_t * pnode;

        memset(&node, 0x00, sizeof(node));
        init_head(tree_t, &head);

        for (i = 0; i < N; ++i) {
                node[i].a = i;
        }
        if (tree_get_root(&head) != NULL) {
                printf("wrong1: tree_get_root\n");
                return;
        }
        tree_add_son(&head, &(node[0].tree));
        tree_add_son(&(node[0].tree), &(node[1].tree));
        tree_add_son(&(node[0].tree), &(node[2].tree));
        tree_add_son(&(node[1].tree), &(node[3].tree));
        tree_add_son(&(node[2].tree), &(node[7].tree));
        tree_add_son(&(node[2].tree), &(node[8].tree));
        tree_add_son(&(node[3].tree), &(node[4].tree));
        tree_add_son(&(node[3].tree), &(node[5].tree));
        tree_add_son(&(node[3].tree), &(node[6].tree));
        tree_add_son(&(node[8].tree), &(node[9].tree));	
	
	tree_del_son_all(&(node[9].tree));	
	
	ptree = head.first_son->first_son->first_son->first_son; 
	if (ptree != NULL) {
		printf("wrong1: tree_del_all\n");
		return ;
	}
	
	tree_del_son_all(&(node[2].tree));
	ptree = head.first_son->first_son;
	if (ptree->brother_right != ptree->brother_left) {
		printf("wrong2: tree_del_all\n");
		return ;
	}
	pnode = entry(ptree, node_t, tree);
	if (pnode->a != 1) {
		printf("wrong3: tree_del_all\n");
		return ;
	}
	tree_del_son_all(&(node[5].tree));
	if (head.first_son->first_son->first_son->first_son->brother_right != head.first_son->first_son->first_son->first_son->brother_left) {
		printf("wrong4: tree_del_all\n");
		return ;
	}
	ptree = head.first_son->first_son->first_son->first_son->brother_right;
	pnode = entry(ptree, node_t, tree);
	if (pnode->a != 4) {
		printf("wrong5: tree_del_all\n");
		return ;
	}

	tree_del_son_all(&(node[1].tree));
	if (head.first_son->first_son != NULL) {
		printf("wrong6: tree_del_all\n");
		return ;
	}
	printf("right: tree_del_all\n");	
}

void check_tree_del_son() {
	tree_t head;
        tree_t * ptree;
        int i = 0;
        node_t node[N];
        node_t * pnode;

        memset(&node, 0x00, sizeof(node));
        init_head(tree_t, &head);

        for (i = 0; i < N; ++i) {
                node[i].a = i;
        }
        if (tree_get_root(&head) != NULL) {
                printf("wrong1: tree_get_root\n");
                return;
        }
        tree_add_son(&head, &(node[0].tree));
        tree_add_son(&(node[0].tree), &(node[1].tree));
        tree_add_son(&(node[0].tree), &(node[2].tree));
        tree_add_son(&(node[1].tree), &(node[3].tree));
        tree_add_son(&(node[2].tree), &(node[7].tree));
        tree_add_son(&(node[2].tree), &(node[8].tree));
        tree_add_son(&(node[3].tree), &(node[4].tree));
        tree_add_son(&(node[3].tree), &(node[5].tree));
        tree_add_son(&(node[3].tree), &(node[6].tree));
        tree_add_son(&(node[8].tree), &(node[9].tree));	

	tree_del_son(&(node[9].tree));	

	ptree = tree_get_son(&(node[8].tree), 0);
	if (ptree != NULL) {
		printf("wrong1: tree_del_son\n");
		return ;
	}

	tree_del_son(&(node[2].tree));
	ptree = tree_get_son(&(node[0].tree), 0);
	if (ptree->father != &(node[0].tree)) {
		printf("wrong2: tree_del_son\n");
		return ;
	}
	pnode = entry(ptree, node_t, tree);
	if (pnode->a != 8) {
		printf("wrong3: tree_del_son\n");
		return ;
	}
	
	ptree = tree_get_son(&(node[0].tree), 1);
	if (ptree->father != &(node[0].tree)) {
		printf("wrong4: tree_del_son\n");
		return ;
	}
	pnode = entry(ptree, node_t, tree);
	if (pnode->a != 7) {
		printf("wrong5: tree_del_son\n");
		return ;
	}
	
	ptree = tree_get_son(&(node[0].tree), 2);
	if (ptree->father != &(node[0].tree)) {
		printf("wrong8: tree_del_son\n");
		return ;
	}
	pnode = entry(ptree, node_t, tree);
	if (pnode->a != 1) {
		printf("wrong9: tree_del_son\n");
		return ;
	}

	ptree = tree_get_son(&(node[0].tree), 3);
	if (ptree != NULL) {
		printf("wrong10: tree_del_son\n");
		return ;
	}

	tree_del_son(&(node[5].tree));
	ptree = tree_get_son(&(node[3].tree), 0);
	if (ptree->father != &(node[3].tree)) {
		printf("wrong11: tree_del_son\n");
		return ;
	}
	pnode = entry(ptree, node_t, tree);
	if (pnode->a != 6) {
		printf("wrong12: tree_del_son\n");
		return ;
	}
	ptree = tree_get_son(&(node[3].tree), 1);
	if (ptree->father != &(node[3].tree)) {
		printf("wrong13: tree_del_son\n");
		return ;
	}
	pnode = entry(ptree, node_t, tree);
	if (pnode->a != 4) {
		printf("wrong14: tree_del_son\n");
		return ;
	}
	ptree = tree_get_son(&(node[3].tree), 2);
	if (ptree != NULL) {
		printf("wrong15: tree_del_son\n");
		return ;
	}

	tree_del_son(&(node[1].tree));
	ptree = tree_get_son(&(node[0].tree), 0);
	if (ptree->father != &(node[0].tree)) {
		printf("wrong15: tree_del_son\n");
		return ;
	}
	pnode = entry(ptree, node_t, tree);
	if (pnode->a != 8) {
		printf("wrong16: tree_del_son\n");
		return ;
	}
	ptree = tree_get_son(&(node[0].tree), 1);
	if (ptree->father != &(node[0].tree)) {
		printf("wrong17: tree_del_son\n");
		return ;
	}
	pnode = entry(ptree, node_t, tree);
	if (pnode->a != 7) {
		printf("wrong18: tree_del_son\n");
		return ;
	}
	ptree = tree_get_son(&(node[0].tree), 2);
	if (ptree->father != &(node[0].tree)) {
		printf("wrong19: tree_del_son\n");
		return ;
	}
	pnode = entry(ptree, node_t, tree);
	if (pnode->a != 3) {
		printf("wrong20: tree_del_son\n");
		return ;
	}
	
	printf("right: tree_del_son\n");
}

void check_tree() {
	tree_t head;
        tree_t * ptree;
        int i = 0;
        node_t node[N];
        node_t * pnode;

        memset(&node, 0x00, sizeof(node));
        init_head(tree_t, &head);

        for (i = 0; i < N; ++i) {
                node[i].a = i;
        }
        tree_add_son(&head, &(node[0].tree));
        tree_add_son(&(node[0].tree), &(node[1].tree));
        tree_add_son(&(node[0].tree), &(node[2].tree));
        tree_add_son(&(node[1].tree), &(node[3].tree));
        tree_add_son(&(node[2].tree), &(node[7].tree));
        tree_add_son(&(node[2].tree), &(node[8].tree));
        tree_add_son(&(node[3].tree), &(node[4].tree));
        tree_add_son(&(node[3].tree), &(node[5].tree));
        tree_add_son(&(node[3].tree), &(node[6].tree));
        tree_add_son(&(node[8].tree), &(node[9].tree));
	
	printTree(&head);
}
int main() {
	
	check_tree_is_empty();		
	check_tree_empty();
	check_tree_is_head();
	check_tree_add_son();
	check_tree_is_exist();
	check_tree_is_root();
	check_tree_get_son();
	check_tree_get_father();
	check_tree_get_head();
	check_tree_get_root();
	check_tree_del_son_all();
	check_tree_del_son();
	check_tree();
	return 0;
}
